// ----------------------------------------------------------------------------
// allocator.cpp
// ----------------------------------------------------------------------------
#include <fw/base/runtime/allocator.h>
#include <fw/base/runtime/registration_object.h>
#include <fw/base/core/macros.h>
#include <fw/base/core/assertion.h>
#include <fw/base/core/stdinteger.h>
#include <fw/base/concurrent/mutex.h>
#include <cstdlib>
#include <map>
#include <new>

namespace fw
{
	// メモリアロケーション追跡の実装.
	class MemoryTrackerImpl
	{
	private:
		struct Record
		{
			uint32_t	m_id;
			int			m_line;
			size_t		m_bytes;
			const char*	m_filename;
			
			Record()
			: m_id		(0)
			, m_line	(0)
			, m_bytes	(0)
			, m_filename(0)
			{
			}
			
			Record(uint32_t id, size_t bytes, const char* filename, int line)
			: m_id		(id)
			, m_line	(line)
			, m_bytes	(bytes)
			, m_filename(filename)
			{
			}
		}; // struct Record
		typedef std::map<const void*, Record>	AllocationMap;
		typedef fw::Mutex						AllocationMutex;
		typedef fw::MutexLocker					AllocationMutexLocker;
		
		AllocationMap	m_allocations;
		size_t			m_totalAllocations;
		uint32_t		m_allocationID;
		AllocationMutex m_mutex;
		
	public:
		MemoryTrackerImpl()
		: m_totalAllocations(0)
		, m_allocationID(0)
		, m_mutex("MemoryTrackerMutex")
		{
		}
		
		~MemoryTrackerImpl()
		{
		}
		
		void	RecordAlloc(const void* memory, size_t size, const char* filename, int line)
		{
			if(!memory)
			{
				return;
			}
			AllocationMutexLocker locker(m_mutex);
			
			// 二重に記録されていないかチェックする.
			FW_ASSERT(m_allocations.find(memory) == m_allocations.end());
			
			// メモリアロケーションを記録する.
			m_allocations[memory] = Record(m_allocationID, size, filename, line);
			m_totalAllocations	 += size;
			m_allocationID++;
		}
		
		void	RecordDealloc(const void* memory)
		{
			AllocationMutexLocker locker(m_mutex);
			
			// 二重に開放されていないかチェックする.
			AllocationMap::iterator it=m_allocations.find(memory);
			FW_ASSERT(it!=m_allocations.end());
			
			// メモリアロケーションの記録を削除.
			m_totalAllocations -= it->second.m_bytes;
			m_allocations.erase(it);
		}
		
		void	Report()
		{
			FW_PRINTF("----------------------------------------------------------\n");
			if(m_allocations.empty())
			{
				FW_PRINTF("MemoryTracker : No memory leak was detected.\n");
			}
			else
			{
				FW_PRINTF("MemoryTracker : %d memory block(s) were detected.\n", m_allocations.size());
				size_t totalAllocationLeft = 0;
				for(AllocationMap::const_iterator it=m_allocations.begin(); it!=m_allocations.end(); ++it)
				{
					const Record& record = it->second;
					if(!record.m_filename)
					{	/*
						 トラッキング不可能なメモリ :
						 
						 以下のような理由が考えられる.
						 ・提供されたマクロを利用していない場合.
						 ・ライブラリ側は FW_MEMORY_TRACKING == 1 を定義してビルドしたが、
						 ライブラリを利用するプロジェクトが FW_MEMORY_TRACKING == 1 を定義していない場合.
						 
						 この場合、記録無しのメモリ確保メソッドにブレークポイントをつける等の
						 方法でこのメモリを発見できるかもしれない.
						 */
						FW_PRINTF("\tUnknown(----) %dbytes. ID[0x%08x]\n", record.m_bytes, record.m_id);
					}
					else
					{
						FW_PRINTF("\t%s(%d) %dbytes. ID[0x%08x]\n", record.m_filename, record.m_line, record.m_bytes, record.m_id);
					}
					totalAllocationLeft += record.m_bytes;
				}
				FW_PRINTF("\nLeak subtotal : %dbytes.\n\n", totalAllocationLeft);
			}
		}
		
		size_t	GetTotalAllocations() const
		{
			return m_totalAllocations;
		}
		
	}; // class MemoryTrackerImpl
	
	MemoryTracker::MemoryTracker(const char* trackerName)
	: m_trackerName(trackerName)
	, m_impl(0)
	{
		m_impl = new MemoryTrackerImpl;
	}
	
	MemoryTracker::~MemoryTracker()
	{
		FW_ASSERT(m_impl);
	#if defined(FW_MEMORY_TRACKING)
		FW_PRINTF("Section : [%s]\n", m_trackerName);
		m_impl->Report();
	#endif
		delete m_impl;
	}
	
	void MemoryTracker::RecordAlloc(const void* p, size_t size, const char* file, int line)
	{
		FW_ASSERT(m_impl);
		m_impl->RecordAlloc(p, size, file, line);
	}
	void MemoryTracker::RecordDealloc(const void* p)
	{
		FW_ASSERT(m_impl);
		m_impl->RecordDealloc(p);
	}
	
	namespace
	{
		struct Header
		{
			size_t size;
		}; // struct Header
		
		const size_t HEADER_PAD_VALUE = -1;
		
		FW_FORCE_INLINE void* DataPointer(Header* header, size_t align)
		{
			void* p = header + 1;
			return Memory::AlignForward(p, align);
		}
		
		FW_FORCE_INLINE Header* HeaderPointer(void* data)
		{
			size_t* p = reinterpret_cast<size_t*>(data);
			while(p[-1] == HEADER_PAD_VALUE)
			{
				--p;
			}
			return (Header*)p - 1;
		}
		
		FW_FORCE_INLINE void FillHeader(Header* header, void* data, size_t size)
		{
			header->size = size;
			size_t* p = reinterpret_cast<size_t*>(header+1);
			while(p<data)
			{
				*p++ = HEADER_PAD_VALUE;
			}
		}
		
		class MallocAllocator : public Allocator
		{
		private:
            typedef fw::Mutex						AllocationMutex;
            typedef fw::MutexLocker					AllocationMutexLocker;
            
			size_t			m_totalAllocated;
			MemoryTracker	m_tracker;
            AllocationMutex m_mutex;
			
			static FW_FORCE_INLINE size_t SizeWithPadding(size_t size, size_t align)
			{
				return size + align + sizeof(Header);
			}
			
		public:
			
			 MallocAllocator()
			: m_totalAllocated(0)
			, m_tracker("DefaultAllocator")
            , m_mutex("MallocAllocator")
			{
			}
			
			~MallocAllocator()
			{
				if(m_totalAllocated)
				{
					FW_PRINTF("Memory leak detected. [%dbytes left(include memory tag info)]\n", m_totalAllocated);
				}
			}
			
			virtual void* Allocate(size_t size, size_t alignment)
			{
                AllocationMutexLocker locker(m_mutex);
                
				const size_t ts = SizeWithPadding(size, alignment);
				Header* h = reinterpret_cast<Header*>(malloc(ts));
				void* p = DataPointer(h, alignment);
				FillHeader(h, p, ts);
				m_totalAllocated += ts;
				return p;
			}
			
			virtual void Deallocate(void* memoryBlock)
			{
				if(!memoryBlock)
				{
					return;
				}
                AllocationMutexLocker locker(m_mutex);
                
				Header* h = HeaderPointer(memoryBlock);
				m_totalAllocated -= h->size;
				free(h);
			}
			
			size_t	TotalAllocatedSize() const
			{
				return m_totalAllocated;
			}
			
			void RecordAlloc(const void* p, size_t size, const char* file, int line)
			{
				m_tracker.RecordAlloc(p, size, file, line);
			}
			
			void RecordDealloc		(const void* p)
			{
				m_tracker.RecordDealloc(p);
			}
			
		}; // class MallocAllocator
		
		// リングバッファ形式のメモリアロケータ.
		// 短い期間で確保/開放を行うメモリにはこちらのアロケータを使用する.
		class RingAllocator : public Allocator
		{
		private:
            typedef fw::Mutex						AllocationMutex;
            typedef fw::MutexLocker					AllocationMutexLocker;

			Allocator&	m_backing; // 親アロケータへの参照.
			char*		m_begin;
			char*		m_end;
			char*		m_allocate;
			char*		m_free;
            AllocationMutex m_mutex;

			bool PointerInUse(void* p)
			{
				if(m_free == m_allocate)
				{
					return false;
				}
				if(m_allocate > m_free)
				{
					return p >= m_free && p < m_allocate;
				}
				return p >= m_free || p < m_allocate;
			}

		#if defined(FW_TARGET_64BIT)
			static const size_t kMarkBit = 0x8000000000000000ul;
		#elif defined(FW_TARGET_32BIT)
			static const size_t kMarkBit = 0x80000000;
		#endif
			static const size_t kMaskBit =~(kMarkBit);
			
		public:
			RingAllocator(Allocator& backing, size_t size)
			: m_backing(backing)
            , m_mutex("RingAllocator")
			{
				m_begin = reinterpret_cast<char*>(m_backing.Allocate(size));
				FW_ASSERT(m_begin);
				m_end = m_begin + size;
				m_allocate = m_free = m_begin;
			}
			
			~RingAllocator()
			{
				FW_ASSERT(m_free == m_allocate);
				m_backing.Deallocate(m_begin);
			}
			
			virtual void* Allocate(size_t size, size_t alignment)
			{
                AllocationMutexLocker lock(m_mutex);
                
				FW_ASSERT((alignment%4)==0);
				size_t allocateSize = ((size+(alignment-1))/alignment)*alignment;
				
				char* p = m_allocate;
				Header* h = reinterpret_cast<Header*>(p);
				char* data = reinterpret_cast<char*>(DataPointer(h, alignment));
				p = data + allocateSize;
				
				// リングバッファの終端を超えた場合、先頭からメモリ確保をやり直す.
				// (m_endは確保されたメモリの外側であることに注意.) 
				if(p >= m_end)
				{
					h->size = (m_end - reinterpret_cast<char*>(h)) | kMarkBit;
					
					p = m_begin;
					h = reinterpret_cast<Header*>(p);
					data = reinterpret_cast<char*>(DataPointer(h, alignment));
					p = data + allocateSize;
				}
				// ポインタ位置のデータがまだ使用中ならこのアロケーションは使用不可. 
				if (PointerInUse(p))
				{
					return m_backing.Allocate(size, alignment);
				}
				
				FillHeader(h, data, p - reinterpret_cast<char*>(h));
				m_allocate = p;
				return data;
			}
			
			virtual void Deallocate(void* p)
			{
				if(!p)
				{
					return;
				}
				if(p<m_begin || p>=m_end)
				{
					m_backing.Deallocate(p);
					return;
				}
                AllocationMutexLocker lock(m_mutex);
                
				// 使用済みフラグを設定する.
				Header* h = HeaderPointer(p);
				FW_ASSERT((h->size & kMarkBit) == 0);
				h->size |= kMarkBit;
				
				// フリーポインタを前進させる.
				while(m_free != m_allocate)
				{
					Header* nh = reinterpret_cast<Header*>(m_free);
					if((nh->size & kMarkBit) == 0)
					{
						break;
					}
					m_free += (nh->size & kMaskBit);
					FW_ASSERT(m_free<=m_end);
					if(m_free == m_end)
					{
						m_free = m_begin;
					}
				}
			}
			
			virtual size_t TotalAllocatedSize() const
			{
				return m_end - m_begin;
			}
			
		}; // class RingAllocator
		
		class MemoryAllocatorGlobal : public Singleton<MemoryAllocatorGlobal>
		{
		public:
			static const int ALLOCATOR_MEMORY_SIZE = sizeof(MallocAllocator) + sizeof(RingAllocator);
			char buffer[ALLOCATOR_MEMORY_SIZE];
			MallocAllocator* m_defaultAllocator;
			RingAllocator* m_ringAllocator;
			
			MemoryAllocatorGlobal()
			: m_defaultAllocator(0)
			, m_ringAllocator(0)
			{
			}
			
		}; // class MemoryAllocatorGlobal
		
		MemoryAllocatorGlobal g_memoryAllocatorGlobal;
		
	} // unnamed namespace
	
	namespace MemorySubsystem
	{
		void Initialize(size_t scratchBufferSize)
		{
			FW_ASSERT(scratchBufferSize>0);
			
			char* p = g_memoryAllocatorGlobal.buffer;
			g_memoryAllocatorGlobal.m_defaultAllocator = new (p) MallocAllocator();
			p += sizeof(MallocAllocator);
			g_memoryAllocatorGlobal.m_ringAllocator = new (p) RingAllocator(MemorySubsystem::DefaultAllocator(), scratchBufferSize);
		}
		
		void Terminate()
		{
			g_memoryAllocatorGlobal.m_ringAllocator->~RingAllocator();
			g_memoryAllocatorGlobal.m_defaultAllocator->~MallocAllocator();
		}
		
		Allocator& DefaultAllocator()
		{
			FW_ASSERT(g_memoryAllocatorGlobal.m_defaultAllocator);
			return (*g_memoryAllocatorGlobal.m_defaultAllocator);
		}
		
		Allocator& ScratchAllocator()
		{
			FW_ASSERT(g_memoryAllocatorGlobal.m_ringAllocator);
			return (*g_memoryAllocatorGlobal.m_ringAllocator);
		}
		
		void MemoryAllocatorSubsystem(FW_OBJECT_OPERATION operation)
		{
			if(operation == FW_REGISTER_ON_INITIALIZE)
			{
				Initialize(kScratchBufferSize);
			}
			else if(operation == FW_REGISTER_ON_DESTROY)
			{
				Terminate();
			}
		}
		FW_REGISTER_FUNCTION(MemoryAllocatorSubsystem, FW_REGISTER_OBJECT_PRIO_MEMORY_ALLOCATION);
		
	} // namespace MemorySubsystem
	
} // namespace fw 
